package LeetcodeTest_fifteen;
//对链表元素进行插入排序
import java.util.Scanner;

public class insertionSortList
{
    public static void main(String[] args)
    {
        ListNode head=null;
        head=solution.createListNode();
        head=solution.insertionSortList(head);
        ListNode p=head;
        while(p!=null)
        {
            System.out.println(p.val);
            p=p.next;
        }
    }
}
class solution
{
    public static ListNode insertionSortList(ListNode head)
    {
        if(head==null||head.next==null)
            return head;
        ListNode root=new ListNode(0);
        root.next=head;
        ListNode parent1=head;//parent1节点p1的前趋
        ListNode p1=parent1.next;
        ListNode parent2=root;//parent2节点p2的前趋
        ListNode p2=parent2.next;
        while(p1!=null)
        {
            while(p1!=p2)
            {
                if (p1.val < p2.val)
                {
                    if (p1.next == null)
                    {
                        ListNode p = new ListNode(p1.val);
                        p.next = p2;
                        parent2.next = p;
                        p1 = null;
                        parent1.next=p1;
                        break;
                    }
                    else
                    {
                        ListNode p = new ListNode(p1.val);
                        p.next = parent2.next;
                        parent2.next = p;
                        p1=p1.next;
                        parent1.next=p1;
                        break;
                    }
                }
                parent2=parent2.next;
                p2=p2.next;
            }
            if(p1==p2)
            {
                p1=p1.next;
                parent1=parent1.next;
            }
            parent2=root;
            p2=parent2.next;
        }
        return root.next;
    }
    public static ListNode createListNode()
    {
        Scanner reader=new Scanner(System.in);
        ListNode head=null;
        ListNode tail=null;
        head=new ListNode(0);
        tail=head;
        for(int i=0;i<5;i++)
        {
            ListNode p=new ListNode(reader.nextInt());
            tail.next=p;
            tail=tail.next;
        }
        return head.next;
    }
}
class ListNode
{
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}